The present invention relates to a graphic painting method for painting or filling a graphic by restoring contour of a graphic from bending points of said graphic.
The processing for painting a graphic is a very important technique in computer graphics, and it is indispensable for the case where code information is developed in raster image. In particular, it is used in recent years for painting characters in case outline font is used. Various methods have been proposed for painting graphic. An ordered edge list algorithm is known as a painting method with side applications. A brief description of this method is given below. In the present specification, the term "graphic" also includes characters, symbols, etc.
FIG. 8 is a flow chart of painting processes according to the ordered edge list algorithm. It is supposed that a list of coordinate data of 7 vertexes shown by (1)-(7) is given in FIG. 9. All of the vertexes are connected sequentially to form contour points. For the intersection points of these contour points with straight lines where Y coordinates in memory is N (N is an integer of 0 or more.), X coordinates are obtained. (Hereinafter these straight lines are referred as "effective scan lines".) These X coordinates are matched with Y coordinates and are registered on an ordered edge list (hereinafter referred as "edge list") (Step S20). In this case, the intersection points such as (1), (3) or (4), which are maximal or minimal points in Y direction, are counted as two points. The intersection points such as (2) or (7), which are neither a maximal point nor a minimal point, are counted as one point without duplication. The intersection points such as (5) or (6), which are maximal point or minimal point in X direction, are counted as one point.
In the above procedure, for sequentially tracing countour points of the graphic from coordinate data of the given vertexes, Bresenham's linear interpolation can be used, for example. It is needless to say that any other method can be used if contour points of the graphic can be obtained. In FIG. 9, the X direction represents a main scanning direction in a display unit, page printer, etc., and the Y direction represents an auxiliary scanning direction. The same applies hereinafter.
By performing Step S20 between all of the vertexes, X coordinates of all intersection points of graphic contour with effective scan lines as shown by circles in FIG. 10 are obtained (Step S21). By the above procedure, X coordinates of all intersection points matching with Y coordinates are registered in an edge list as shown in FIG. 11A.
Next, as shown in FIG. 11B, X coordinates registered in the edge list are rearranged in the ascending order of Y coordinates. Further, as shown in FIG. 11C, X coordinates are rearranged with respect to each Y coordinate, and a coordinate list of intersection points is prepared as shown in FIG. 11D (Step S22). Then, looking at the edge list thus rearranged from the top, pairs of X coordinates including adjacent odd and even numbers are selected, such as 1st and 2nd, or 3rd and 4th, with respect to each Y coordinate. By setting a predetermined pixel pattern between these pairs of X coordinates, painting or filling of the graphic is performed (Step S23). For example, in FIG. 11D, X coordinates from 3 to 6 are painted at the position Y=2. At the position Y=4, X coordinates from 3 to 6 and from 8 to 10 are painted. In this way, the graphic is painted as shown in FIG. 12.
However, in the graphic painting by conventional ordered edge list algorithm, painting cannot be achieved in case the data of X coordinates for the intersection points of the contour with the effective scan lines exceed memory capacity to store the edge list.
For example, in case outline font is developed in a bit map, a memory to store the edge list is usually designed in such capacity that a complicated Chinese character having the highest number of intersections of contour with the effective scan lines can be developed in bit map data. If more complicated characters, symbols, or graphics are to be prepared, it is no longer possible to develop in bit map data. Of course, such a problem can be avoided by using a memory having very large capacity, but this leads to very expensive cost. In case of small-scale graphic processing units such as word processors or personal computers, it is impossible or impractical to maintain memory area abundant enough to store such an edge list.